//class Solution1 {
//    public ListNode sortList(ListNode head) {
//           if(head == null || head.next == null){
//            return head ;
//           }
//           ListNode mod = head ;
//           ListNode fast = head.next ;
//           while(fast != null && fast.next != null){
//            mod = mod.next ;
//            fast = fast.next.next ;
//           }
//           ListNode tmp = mod.next ;
//           mod.next = null ;
//          ListNode left = sortList(head);
//          ListNode right = sortList(tmp);
//          ListNode newHead = new ListNode(0);
//          ListNode ret = newHead;
//
//          while(left != null && right != null){
//                if(left.val < right.val){
//                  ret.next = left;
//                  left = left.next ;
//                }else{
//                   ret.next = right;
//                   right = right.next ;
//                }
//                ret = ret.next ;
//          }
//         ret.next =  (left != null) ? left : right ;
//         return newHead.next ;
//    }
//}
//class Solution {
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        ListNode newHead = new ListNode(0);
//        ListNode ret = newHead;
//        while(list1 != null && list2 != null){
//            if(list1.val < list2.val){
//                ret.next = list1 ;
//                list1 = list1.next ;
//            }else{
//                ret.next = list2 ;
//                list2 = list2.next ;
//            }
//            ret = ret.next ;
//        }
//        ret.next = (list1 != null) ? list1 : list2 ;
//        return newHead.next ;
//
//    }
//}
//public class Solution {
//    public ListNode deleteDuplication(ListNode pHead) {
//        if(pHead == null)return null ;
//        ListNode newHead = null ;
//        ListNode last = null ;
//        ListNode cur = pHead;
//        while(cur != null){
//            ListNode curNext = cur.next ;
//            while(curNext != null && curNext.val == cur.val){
//                curNext = curNext.next ;
//            }
//            if(cur.next == curNext){
//                if(newHead == null){
//                    newHead = cur ;
//                    last = cur ;
//                }else{
//                    last.next = cur ;
//                    last = last.next ;
//                }
//            }
//            cur = curNext;
//        }
//        if(last != null)last.next = null ;
//        return newHead;
//    }
//}
//class Solution {
//    public ListNode reverseList(ListNode head) {
//        ListNode newHead = null;
//        ListNode cur = head ;
//        while(cur != null){
//            ListNode curNext = cur.next ;
//            cur.next = newHead ;
//            newHead = cur ;
//            cur = curNext;
//        }
//        return newHead ;
//    }
//}
//public class Solution {
//    public ListNode detectCycle(ListNode head) {
//        if(head == null) return null ;
//        ListNode slow = head ;
//        ListNode fast = head ;
//        while(fast != null && fast.next != null){
//            slow = slow.next ;
//            fast = fast.next.next ;
//            if(fast == slow){
//                break ;
//            }
//        }
//        if(fast == null || fast.next == null){
//            return null ;
//        }
//        slow = head ;
//        while(slow != fast){
//            slow = slow.next ;
//            fast = fast.next ;
//        }
//
//        return slow;
//
//    }
//}